//
// Created by DengLibin on 2018/12/16 0016.
//

/**
 *八皇后问题
 */
#include <iostream>
using namespace std;

int num_ = 0;

//判断是否有危险 行 列 棋盘
bool notDenger(int row, int n, int(*chess)[8])
{
    //判断列方向
    for (int i = 0; i < 8; i++)
    {
        if (chess[i][n] != 0) //该列上有皇后了
        {
            return false;
        }
    }
    //判断左上方
    for (int i = row,j=n; i >=0 && j>=0; i--,j--)
    {
        if (chess[i][j] != 0)
        {
            return false;
        }
    }
    //判断右下方
    for (int i = row, j = n; i < 8 && j < 8; i++, j++)
    {
        if (chess[i][j] != 0)
        {
            return false;
        }
    }
    //判断右上方
    for (int i = row, j = n; i >= 0 && j < 8; i--, j++)
    {
        if (chess[i][j] != 0)
        {
            return false;
        }
    }

    //判断左下方
    for (int i = row, j = n; i < 8 && j >= 0; i++, j--)
    {
        if (chess[i][j] != 0)
        {
            return false;
        }
    }
    return true;

}

//参数 row:起始行 n:列 chess: 棋盘
void EightQueen(int row, int n, int chess[8][8])
{
    int tempChess[8][8]; //棋盘
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            tempChess[i][j] = chess[i][j];
        }
    }
    if (row == 8) //到第8行截止
    {
        cout << "第："<< num_ <<"种" << endl;
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                cout << tempChess[i][j]<<" ";
            }
            cout << endl;
        }
        cout << endl << endl;
        num_++;
    }
    else
    {
        for (int i = 0; i < n; i++) //8列
        {
            if (notDenger(row, i,tempChess)) //每一列都判断是否危险
            {
                //如果不危险，当前行所有列先设为0
                for (int j = 0; j < 8; j++)
                {
                    tempChess[row][j] = 0;
                }
                //标明当前行 皇后的位置
                tempChess[row][i] = 1;//皇后的位子
                //继续下一行
                EightQueen(row + 1, n, tempChess);
            }
        }
    }
}
int main39_1(int argc, char * argv[])
{
    cout <<"八皇后问题："<<endl;
    int chess[8][8];//棋盘 8 *8
    //初始化
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j< 8; j++)
        {
            chess[i][j] = 0;
        }
    }
    EightQueen(0,8,chess);
    cout << "总共有"<<num_<<"种解决方式！" << endl;
    return 0;
}